/*
 * Treap.h
 * This file is part of Jamming
 *
 * Copyright (C) 2012 - Yi
 *
 * Jamming is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Jamming is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Jamming. If not, see <http://www.gnu.org/licenses/>.
 */


#ifndef __TREAP_H__
#define __TREAP_H__

#ifdef __USE__BOOST__
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#else
#include <stdlib.h>
#endif 

#ifdef __DEBUG__
#include <queue>
#include <utility>
#include <iostream>
#endif

#include <time.h>
namespace Tree
{
    template <typename _TypeData>
    class Treap {
        struct Node {
            int weight;
            _TypeData data;
            Node* child[2];
        };
        static const int LEFT=0,RIGHT=1;
        Node* myroot;
#ifdef __USE__BOOST__
        boost::mt19937 gen;
        boost::uniform_int<> dist;
#endif
        inline void rotate(Node* &ptrBaseNode,int right) {
#if __DEBUG__ > 1
            std::cout<<"Rotate "<<ptrBaseNode<<"("<<ptrBaseNode->data<<") "<<(right?"right":"left")<<std::endl;
#endif
            Node* ptrNewBase=ptrBaseNode->child[right];
            ptrBaseNode->child[right]=ptrNewBase->child[!right];
            ptrNewBase->child[!right]=ptrBaseNode;
            //swap ptrNewBase and ptrBaseNode
            ptrBaseNode=ptrNewBase;
        };
        void insertTosubtree(Node* &root,_TypeData &data) {
            if(!root) { 
                Node* newNode= new Node;
                newNode->data=data;
                newNode->child[LEFT]=newNode->child[RIGHT]=NULL;
#ifdef __USE__BOOST__
                newNode->weight=dist(gen);
#else
                newNode->weight=rand()*rand();
#endif
#if __DEBUG__ > 1
                std::cout<<"Insert new node "<<newNode<<":"<<data<<"("<<newNode->weight<<")"<<std::endl;
#endif
                root=newNode;
                return;
            }
            int isRight=data > root->data;
#if __DEBUG__ > 1
                std::cout<<"Insert into "<<(isRight?"right":"left")<<" of "<<root<<"("<<root->data<<")"<<std::endl;
#endif
            // if equal ? ---> raise keyExists? important! node with same key prevents balancing.
            if( data == root->data ) return;
            insertTosubtree(root->child[isRight],data);
            //maintainance
#if __DEBUG__ > 1
            if(root->child[isRight]->weight < root->weight) {
                print();
                rotate(root,isRight);
                print();
            }
#else 
            if(root->child[isRight]->weight < root->weight) rotate(root,isRight);
#endif
        };
        void deleteFromTree(Node* &root,_TypeData &data) {
        	if(root==NULL) return;
		    if(root->data==data) {
				bool isRight;
				if(!root->child[RIGHT]) { 
				    isRight=1;
				} else if(!root->child[LEFT]) {
				    isRight=0;
				} else isRight=root->child[RIGHT]->weight<root->child[LEFT]->weight;
				if(root->child[RIGHT]==NULL&&root->child[LEFT]==NULL)
				{
#if __DEBUG__ > 1
			    	std::cout<<"Delete node "<<root<<"("<<data<<")"<<std::endl;
#endif
					delete root;
					root=NULL;
					return;
				}
				rotate(root,!isRight);
				#if __DEBUG__ > 1
                print();
				#endif
				deleteFromTree(root->child[isRight],data);
			} else {
				bool isRight=data>root->data;
				deleteFromTree(root->child[isRight],data);
			}
        }
        void deleteSubtree(Node* &ptrNodeToDelete) {
            if(ptrNodeToDelete->child[LEFT]!=NULL) deleteSubtree(ptrNodeToDelete->child[LEFT]);
            if(ptrNodeToDelete->child[RIGHT]!=NULL) deleteSubtree(ptrNodeToDelete->child[RIGHT]);
#if __DEBUG__ > 1
            std::cout<<"Delete "<<ptrNodeToDelete<<":"<<ptrNodeToDelete->data<<std::endl;
#endif
            if(ptrNodeToDelete!=NULL) delete (ptrNodeToDelete);
        };
        public:
        Treap() {
        myroot=NULL;
#ifdef __USE__BOOST__
            gen.seed(time(0));
            dist=boost::uniform_int<>(1,5434432);
#else
            srand(time(0));
#endif
        }
        ~Treap() {
#ifdef __DEBUG__
            std::cout<<"Root is: "<<myroot<<std::endl;
#endif
            if(myroot) deleteSubtree(myroot);
            return;
        }
        void insert(_TypeData data) {
            insertTosubtree(myroot,data);
        }
        void remove(_TypeData data) {
            deleteFromTree(myroot,data);
        }
        void split() {
            
        }
        void merge() {
        
        };
#ifdef __DEBUG__
        int maxdepth(Node* root) {
            if(!root) return 0;
            int left=maxdepth(root->child[LEFT]);
            int right=maxdepth(root->child[RIGHT]);
            return left>right? left+1:right+1;
        }
        int size(Node* root) {
            if(!root) return 0;
            return size(root->child[LEFT])+size(root->child[RIGHT])+1;
        }
        void flaten(Node* root) {
            if(!root) return;
            flaten(root->child[LEFT]);std::cout<<root->data<<" ";flaten(root->child[RIGHT]);
        }
        void print() {
            int depth=maxdepth(myroot);
            std::queue< std::pair<std::pair<int,int>,Node*> > NodesList;
            Node* ptrNode=myroot;
            std::pair<std::pair<int,int>,Node*> nodeInfo;
            int level=-1,nth=0,last=0;
            //If empty
            if(!ptrNode) {std::cout<<"Tree Empty."<<std::endl;return;}
            else std::cout<<"Tree: ";
            NodesList.push(std::make_pair(std::make_pair(level+1,nth),myroot));
            while( ! NodesList.empty()) {
                nodeInfo=NodesList.front();
                NodesList.pop();
                if(nodeInfo.first.first > level) {
                    //enter new level
                    std::cout<<std::endl<<"Level "<<level+1<<" : ";
                    for(register int i=0;i<(1<<(depth-level-2))-1;i++) std::cout<<" ";
                    last=0;
                }
                level=nodeInfo.first.first;nth=nodeInfo.first.second;ptrNode=nodeInfo.second;
                for(register int i=0;i<((1<<(depth-level)))*(nth-last)-1;i++) std::cout<<" ";
                if(ptrNode) std::cout<<ptrNode->data;
                else std::cout<<"x";
                //std::cout<<"("<<ptrNode->weight<<")";
                //std::cout<<","<<nth<<","<<last;
                last=nth;
                if( ptrNode->child[LEFT]) NodesList.push(std::make_pair(std::make_pair(level+1,2*nth),ptrNode->child[LEFT]));
                if( ptrNode->child[RIGHT]) NodesList.push(std::make_pair(std::make_pair(level+1,2*nth+1),ptrNode->child[RIGHT]));
            }
            std::cout<<std::endl;
        }
        void printFlat() {
           flaten(myroot);
           std::cout<<std::endl;
        }
        void printDepth() {
            std::cout<<"Max Depth: "<<maxdepth(myroot)<<std::endl;
        }
#endif
    }; /* End of Treap */
}; /* End of Tree */


#endif /* __TREAP_H__ */

